package review;

public class CountSort {
    public static void main(String[] args) {
        int[] nums = {5, 2, 7, 4, 1, 3, 8, 9};
        nums = countSort(nums);

        for (int num : nums) {
            System.out.print(num+" ");
        }
    }


    public static int[] countSort(int[] nums) {
        if (nums.length < 2) {
            return nums;
        }

        int min = nums[0], max = nums[0];

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            if (nums[i] < min) {
                min = nums[i];
            }
        }

        int[] countArr = new int[max - min + 1];
        for (int i = 0; i < nums.length; i++) {
            countArr[nums[i] - min]++;
        }

        for (int i = 1; i < countArr.length; i++) {
            countArr[i] = countArr[i] + countArr[i - 1];
        }

        int[] ans = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int index = countArr[nums[i] - min] - 1;
            ans[index] = nums[i];
            countArr[nums[i] - min]--;
        }
        return ans;
    }
}
